package 树;

import javax.swing.tree.TreeNode;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeMap;

/**
 * https://leetcode-cn.com/problems/delete-node-in-a-bst/
 *
 * 给定一个二叉搜索树的根节点 root 和一个值 key，
 * 删除二叉搜索树中的key对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 *
 * 一般来说，删除节点可分为两个步骤：
 *
 * 首先找到需要删除的节点；
 * 如果找到了，删除它。
 *
 */
public class _450_删除二叉搜索树中的节点 {
   public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
   }

   //该函数定义:从根节点为root的BST中找到val为key的节点并删除，返回删除后的根节点
    public TreeNode deleteNode(TreeNode root, int key) {
       if(root == null) return null;

       //找到的情况
       if(root.val == key){
         //情况1、2：删除叶子节点或者删除度为1的节点
         if(root.left == null) return root.right;
         if(root.right == null) return root.left;

         //情况3:删除度为2的节点的情况,先找到后继节点记录
         TreeNode successor = getSuccessor(root.right);

         //删除这个后继节点
         root.right = deleteNode(root.right, successor.val);

         //断线，连线
         successor.left = root.left;
         successor.right = root.right;

         root = successor;

       //当前节点上的值比key大，去左子树搜索并删除连接
       }else if(root.val>key){
           root.left = deleteNode(root.left,key);

       //当前节点上的值比key小，去右子树搜索并删除连接
       }else{
           root.right = deleteNode(root.right,key);
       }

       return root;

    }

    //找到该节点的后继结点
    private TreeNode getSuccessor(TreeNode node){
       while(node.left!=null){
           node = node.left;
       }
       return node;
    }

}
